翻訳と辞書 Words near each other ・ Berlanguella scopae ・ Berlare ・ Berlats ・ Berlaymont building ・ Berle ・ Berle (surname) ・ Berle Adams ・ Berle Church ・ Berle M. Schiller ・ Berle Sanford Rosenberg ・ Berle-Kari ・ Berlebecke ・ Berleburg Bible ・ Berlei ・ Berlei Building ・ Berlekamp's algorithm ・ Berlekamp–Massey algorithm ・ Berlekamp–Welch algorithm ・ Berlekamp–Zassenhaus algorithm ・ Berleman House ・ Berlencourt-le-Cauroy ・ Berlenga Grande Island ・ Berlengas ・ Berlengas Natural Reserve ・ Berlengas River ・ Berlens ・ Berlenti Abdul Hamid ・ Berlepsch ・ Berlepsch's canastero ・ Berlepsch's tinamou Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Berlekamp's algorithm ： ウィキペディア英語版 Berlekamp's algorithm In mathematics, particularly computational algebra, Berlekamp's algorithm is a well-known method for factoring polynomials over finite fields (also known as ''Galois fields''). The algorithm consists mainly of matrix reduction and polynomial GCD computations. It was invented by Elwyn Berlekamp in 1967. It was the dominant algorithm for solving the problem until the Cantor–Zassenhaus algorithm of 1981. It is currently implemented in many well-known computer algebra systems. ==Overview== Berlekamp's algorithm takes as input a square-free polynomial $f(x)$ (i.e. one with no repeated factors) of degree $n$ with coefficients in a finite field $\backslash mathbb\_q$ and gives as output a polynomial $g(x)$ with coefficients in the same field such that $g(x)$ divides $f(x)$. The algorithm may then be applied recursively to these and subsequent divisors, until we find the decomposition of $f(x)$ into powers of irreducible polynomials (recalling that the ring of polynomials over a finite field is a unique factorization domain). All possible factors of $f(x)$ are contained within the factor ring :$R\; =\; \backslash frac.$ The algorithm focuses on polynomials $g(x)\; \backslash in\; R$ which satisfy the congruence: :$g(x)^q\; \backslash equiv\; g(x)\; \backslash pmod.\backslash ,$ These polynomials form a subalgebra of R (which can be considered as an $n$-dimensional vector space over $\backslash mathbb\_q$), called the ''Berlekamp subalgebra''. The Berlekamp subalgebra is of interest because the polynomials $g(x)$ it contains satisfy :$f(x)\; =\; \backslash prod\_\; \backslash gcd(f(x),g(x)-s).$ In general, not every GCD in the above product will be a non-trivial factor of $f(x)$, but some are, providing the factors we seek. Berlekamp's algorithm finds polynomials $g(x)$ suitable for use with the above result by computing a basis for the Berlekamp subalgebra. This is achieved via the observation that Berlekamp subalgebra is in fact the kernel of a certain $n\; \backslash times\; n$ matrix over $\backslash mathbb\_q$, which is derived from the so-called Berlekamp matrix of the polynomial, denoted $\backslash mathcal$. If $\backslash mathcal=()$ then $q\_$ is the coefficient of the $j$-th power term in the reduction of $x^$ modulo $f(x)$, i.e.: :$x^\; \backslash equiv\; q\_x^\; +\; q\_x^\; +\; \backslash ldots\; +\; q\_\; \backslash pmod.\backslash ,$ With a certain polynomial $g(x)\; \backslash in\; R$, say: :$g(x)\; =\; g\_x^+g\_x^\; +\; \backslash ldots\; +\; g\_0,\backslash ,$ we may associate the row vector: :$g\; =\; (g\_0,\; g\_1,\; \backslash ldots,\; g\_).\backslash ,$ It is relatively straightforward to see that the row vector $g\backslash mathcal$ corresponds, in the same way, to the reduction of $g(x)^q$ modulo $f(x)$. Consequently a polynomial $g(x)\; \backslash in\; R$ is in the Berlekamp subalgebra if and only if $g(\backslash mathcal-I)=0$ (where $I$ is the $n\; \backslash times\; n$ identity matrix), i.e. if and only if it is in the null space of $\backslash mathcal-I$. By computing the matrix $\backslash mathcal-I$ and reducing it to reduced row echelon form and then easily reading off a basis for the null space, we may find a basis for the Berlekamp subalgebra and hence construct polynomials $g(x)$ in it. We then need to successively compute GCDs of the form above until we find a non-trivial factor. Since the ring of polynomials over a field is a Euclidean domain, we may compute these GCDs using the Euclidean algorithm. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Berlekamp's algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.